//  On my honor:
//	
//  - I have not used source code obtained from another student, 
//    or any other unauthorized source, either modified or unmodified.  
//	
//  - All source code and documentation used in my program 
//    is either my original work, or was derived by me from the source
//    code published in the textbook for this course.
//	
//  - I have not discussed coding details about this project with anyone
//    other than my instructor, ACM/UPE tutors or the GTAs assigned to this
//    course. I understand that I may discuss the concepts of this program
//    with other students, and that another student may help me debug my
//    program so long as neither of us writes anything during the discussion
//    or modifies any computer file during the discussion.  I have violated
//    neither the spirit nor letter of this restriction.

import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.PrintWriter;

public class Heapsort {

	public static void main(String[] args) {
		BufferPool heap = null;
		FileOutputStream statFile = null;
		PrintWriter printer = null;
		boolean parsed = true;
		long heapSize = 0;
		int bufferCount = 0;

		String fileName = args[0];

		// parse arguments and create instances as needed
		// attempt to make the buffer pool for access to "heap" file
		try {
			bufferCount = Integer.parseInt(args[1]);
		} catch (NumberFormatException e) {
			System.err
					.println("Incorrect format.  Please invoke heapsort in the form:");
			System.err
					.println("\theapsort <data-file-name> <numb-buffers> <stat-file-name>");
			System.err.println("\n");
			parsed = false;
		}

		// check number of buffers constraint
		if (parsed && bufferCount < 1 || bufferCount > 20) {
			System.err
					.println("Buffer count out of bounds.  Please specify <numb-buffers>");
			System.err.println("as an integer between 1 and 20 inclusive.");
			parsed = false;
		}

		// create a BufferPool for "heap" (file) access
		if (parsed)
			try {
				heap = new BufferPool(bufferCount, fileName);
			} catch (FileNotFoundException e) {
				System.err.printf("File not found: %s\n", fileName);
				parsed = false;
			}

		// try to get the heap size
		if (parsed)
			try {
				heapSize = heap.heapSize();
			} catch (IOException e) {
				System.err.println("Error while reading from input file.\n");
				System.err
						.println("heapsort could not be run because of one or more errors.");
				parsed = false;
			}

		fileName = args[2];

		// attempt to open file for appended output
		if (parsed)
			try {
				statFile = new FileOutputStream(fileName, true);
				printer = new PrintWriter(statFile);
			} catch (FileNotFoundException e) {
				System.err.printf(
						"File could not be opened or created for write: %s\n",
						fileName);
				parsed = false;
			}

		// run the heapify/sort process
		if (parsed) {
			long execTime = 0;
			try {
				execTime = sort(heap, heapSize);
				heap.flush();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}

			// output to stat output file
			printer.println("Sorted file name: " + args[0]);
			printer.println("      Cache Hits: " + heap.getHits());
			printer.println("    Cache Misses: " + heap.getMisses());
			printer.println("      Disk Reads: " + heap.getReads());
			printer.println("     Disk Writes: " + heap.getWrites());
			printer.println("   Heapsort Time: " + execTime + "ms");

			try {
				int count = 0;
				for (long i = 0; i < heap.heapSize(); i += 1024) {
					System.out.printf("K:%6d V:%6d  ", key(heap.read(i)),
							value(heap.read(i)));
					if (++count == 8) {
						System.out.println("");
						count = 0;
					}
				}
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		} else {
			System.err
					.println("heapsort could not be run because of one or more errors.");
		}

		heap.close();
		printer.close();
	}

	private static short key(int ref) {
		return (short) (ref >>> 16);// Integer.valueOf(ref >> 16).shortValue();
	}

	private static short value(int ref) {
		return (short) (ref & 0x0000ffff);
	}

	private static void heapify(BufferPool heap, long size) throws IOException {
		for (long i = 1; i < size; i++) {
			siftUp(heap, 0, i);
		}
	}

	private static void siftUp(BufferPool heap, long start, long end)
			throws IOException {

		for (long i = end; i > start;) {
			long j = (i - 1) / 2;
			int parent = heap.read(j);
			int child = heap.read(i);

			if (key(parent) < key(child)) {
				int temp = parent;
				heap.write(j, child);
				heap.write(i, temp);
			} else
				return;
			i = j;
		}
	}

	private static void siftDown(BufferPool heap, long start, long end)
			throws IOException {
		for (long i = start; i * 2 + 2 <= end;) {
			long j = i * 2 + 1;
			long k = i;
			int swap = heap.read(i);
			int root = swap;
			int temp = heap.read(j);

			if (swap < temp) {
				k = j;
				swap = temp;
			}

			temp = heap.read(j + 1);
			if (j + 1 < end && swap < temp) {
				k = j + 1;
				swap = temp;
			}

			if (k != i) {
				heap.write(i, swap);
				heap.write(k, root);
				i = k;
			} else
				return;
		}
	}

	/**
	 * @param heap
	 * @param heapSize
	 * @return
	 * @throws IOException
	 */
	private static long sort(BufferPool heap, long heapSize) throws IOException {
		long time = System.currentTimeMillis();

		// heapify the file as an array-implemented max-heap first
		heapify(heap, heapSize);

		// heapsort "heapified" file
		for (long end = heapSize - 1; end > 0; end--) {
			int top = heap.read(0);
			heap.write(0, heap.read(end));
			heap.write(end, top);
			siftDown(heap, 0, end);
		}

		return System.currentTimeMillis() - time;
	}
}
